# Python 2.6.4
# Project Euler, Problem 70
# Copyright 2010 Talha Zaman

#import psyco
#psyco.full()

def sphi(limit):
    sieve = [i for i in range(limit)]
    sieve[0] = sieve[1] = 1
    for i in range(2,limit):
        if sieve[i]<i: continue
        for j in range(2*i, limit, i):
            sieve[j] = sieve[j]*(i-1)/i
        sieve[i] = i-1
    return sieve

def isperm(n, m):
    digits = [0]*10
    for d in str(n): digits[int(d)] += 1
    for d in str(m): digits[int(d)] -= 1
    return not any(digits)

from time import clock
start = clock()
lim = 10000000
minpn = 2
num = 0
s = sphi(lim)
middle = clock()
print "Sieve:", middle-start
for i in range(2, lim):
    npn = i / float(s[i])
    if npn>minpn: continue
    if not isperm(i, s[i]): continue
    minpn = npn
    num = i
stop = clock()
print num
print "Search:", stop-middle
print "Total:", stop-start
